package review.arrays01221012;


import java.sql.Array;
import java.util.ArrayList;
import java.util.Arrays;

/**
 * 实现一个支持动态扩容的数据，
 *
 *  要求： 1：可以实现动态扩容
 *        2：可以根据下标删除元素
 *        3：插入元素功能
 *        4：查找元素功能 （后续接入二分查找）
 */
public class ArraysDemo {

    private int[] arrays;

    private ArrayList<Integer> arrayList;

    private int n; // 数组大小

    private int count; // 数组的实际使用大小,当前使用下标的位置

    public ArraysDemo(int n){
        this.n = n;
        if(n <= 0){
            n = 8;
        }
        this.arrays = new int[n];
    }

    //插入元素
    public int add(int x){
        // 确定是否扩容
        ensureGrow(count+1);
        arrays[count++] = x;
        return x;
    }
    //删除元素, 根据下标删除元素
    public int remove(int i){
        if(i<0 || i>count){
            throw new ArrayIndexOutOfBoundsException();
        }
        if(count == 0){
            System.out.println("当前数组已空，无法删除");
            return -1;
        }

        // 数组删除，将所有元素向左移动一位
        int res = arrays[i];
        while (i<count){
            arrays[i] = arrays[i+1];
            i++;
        }
        arrays[count-1]=0;
        count--;
        return res;
    }

    //查询元素

    private void ensureGrow(int n){
        if(count < n-1){
            return;
        }
        // 每次增加一半扩容
        n  = n + n>>1;
        int[] newArray = new int[n];
        System.arraycopy(arrays,0,newArray,0,count);
        // 使用新数组
        arrays = null;
        arrays = newArray;
    }
}
